package queue;

import queue.pratice.CircularArrayQueueOnTag;

/**
 * 循环数组实现队列
 * @param <T>
 */
public class CircularArrayQueue<T> implements QueueADT<T>{
    private final int DEFAULT_CAPACITY = 100;
    private int front, rear, count;
    private T[] queue;

    public CircularArrayQueue(){
        front = rear = count = 0;
        queue = (T[])(new Object[DEFAULT_CAPACITY]);
    }

    public CircularArrayQueue(int initialCapacity){
        front = rear = count = 0;
        queue = (T[])(new Object[initialCapacity]);
    }

    @Override
    public boolean enqueue(T t) {
        if (count==queue.length){
            System.out.println("队列满，即将扩容"); 
            expandCapacity();
        }
        queue[rear]=t;
        //循环链表指针向后移动一位
        rear=(rear+1)%queue.length;
        count++;
        return true;
    }

    private void expandCapacity() {
        T[] larger = (T[])(new Object[queue.length * 2]);
        for (int scan = 0; scan < count; scan++){
            larger[scan] = queue[front];
            //向后移动front指针，由于是循环数组，不能以index为索引
            front = (front + 1) % queue.length;
        }

        front = 0;
        rear = count;
        queue = larger;
    }

    @Override
    public T dequeue() {
        if(count==0){
            System.out.println("对空");
            return null;
        }

        T result = queue[front];
        queue[front] = null;
        front = (front + 1) % queue.length;
        count--;

        return result;
    }

    @Override
    public T first() {
        return queue[front];
    }

    @Override
    public T last() {
        return queue[rear];
    }
    public void show(){
        for (T t : queue) {
            System.out.println(t);
        }
    }
    public static void main(String[] args) {
        CircularArrayQueue<Integer> queueOnTag = new CircularArrayQueue<>(4);
        queueOnTag.enqueue(1);
        queueOnTag.enqueue(2);
        queueOnTag.enqueue(3);
        queueOnTag.enqueue(4);
        queueOnTag.dequeue();
        queueOnTag.enqueue(5);
        queueOnTag.dequeue();
        queueOnTag.dequeue();
        queueOnTag.enqueue(6);
        queueOnTag.show();

    }
}
